//给你一个字符串 s，找出它的所有子串并按字典序排列，返回排在最后的那个子串。 
//
// 
//
// 示例 1： 
//
// 输入："abab"
//输出："bab"
//解释：我们可以找出 7 个子串 ["a", "ab", "aba", "abab", "b", "ba", "bab"]。按字典序排在最后的子串是 "bab
//"。
// 
//
// 示例 2： 
//
// 输入："leetcode"
//输出："tcode"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 4 * 10^5 
// s 仅含有小写英文字符。 
// 
// Related Topics 双指针 字符串 
// 👍 50 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

/**
 * Java：按字典序排在最后的子串
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P1163_LastSubstringInLexicographicalOrder {
    public static void main(String[] args) {
        Solution solution = new P1163_LastSubstringInLexicographicalOrder().new Solution();
        // 此处开始你的表演
        MyUtil.print(solution.lastSubstring("abab"));
        MyUtil.print(solution.lastSubstring("leetcode"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String lastSubstring(String str) {
            if (str == null || str.length() == 0) {
                return null;
            }
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
            char[] cs = str.toCharArray();
            int N = cs.length;
            for (int i = 0; i < N; i++) {
                max = Math.max(cs[i], max);
                min = Math.min(cs[i], min);
            }
            int[] nums = new int[N];
            for (int i = 0; i < N; i++) {
                nums[i] = cs[i] - min + 1;
            }
            DC3 dc3 = new DC3(nums, max - min + 1);
            return str.substring(dc3.sa[N - 1]);
        }

        public class DC3 {

            public int[] sa;

            /**
             * @param nums 数组中得元素最小值 >=1
             * @param max  数组中的最大值
             */
            public DC3(int[] nums, int max) {
                sa = sa(nums, max);
            }

            private int[] sa(int[] nums, int max) {
                int n = nums.length;
                int[] arr = new int[n + 3];
                for (int i = 0; i < n; i++) {
                    arr[i] = nums[i];
                }
                return skew(arr, n, max);
            }

            private int[] skew(int[] nums, int n, int K) {
                int n0 = (n + 2) / 3, n1 = (n + 1) / 3, n2 = n / 3, n02 = n0 + n2;
                int[] s12 = new int[n02 + 3], sa12 = new int[n02 + 3];
                for (int i = 0, j = 0; i < n + (n0 - n1); ++i) {
                    if (0 != i % 3) {
                        s12[j++] = i;
                    }
                }
                radixPass(nums, s12, sa12, 2, n02, K);
                radixPass(nums, sa12, s12, 1, n02, K);
                radixPass(nums, s12, sa12, 0, n02, K);
                int name = 0, c0 = -1, c1 = -1, c2 = -1;
                for (int i = 0; i < n02; ++i) {
                    if (c0 != nums[sa12[i]] || c1 != nums[sa12[i] + 1] || c2 != nums[sa12[i] + 2]) {
                        name++;
                        c0 = nums[sa12[i]];
                        c1 = nums[sa12[i] + 1];
                        c2 = nums[sa12[i] + 2];
                    }
                    if (1 == sa12[i] % 3) {
                        s12[sa12[i] / 3] = name;
                    } else {
                        s12[sa12[i] / 3 + n0] = name;
                    }
                }
                if (name < n02) {
                    sa12 = skew(s12, n02, name);
                    for (int i = 0; i < n02; i++) {
                        s12[sa12[i]] = i + 1;
                    }
                } else {
                    for (int i = 0; i < n02; i++) {
                        sa12[s12[i] - 1] = i;
                    }
                }
                int[] s0 = new int[n0], sa0 = new int[n0];
                for (int i = 0, j = 0; i < n02; i++) {
                    if (sa12[i] < n0) {
                        s0[j++] = 3 * sa12[i];
                    }
                }
                radixPass(nums, s0, sa0, 0, n0, K);
                int[] sa = new int[n];
                for (int p = 0, t = n0 - n1, k = 0; k < n; k++) {
                    int i = sa12[t] < n0 ? sa12[t] * 3 + 1 : (sa12[t] - n0) * 3 + 2;
                    int j = sa0[p];
                    if (sa12[t] < n0 ? leq(nums[i], s12[sa12[t] + n0], nums[j], s12[j / 3])
                            : leq(nums[i], nums[i + 1], s12[sa12[t] - n0 + 1], nums[j], nums[j + 1], s12[j / 3 + n0])) {
                        sa[k] = i;
                        t++;
                        if (t == n02) {
                            for (k++; p < n0; p++, k++) {
                                sa[k] = sa0[p];
                            }
                        }
                    } else {
                        sa[k] = j;
                        p++;
                        if (p == n0) {
                            for (k++; t < n02; t++, k++) {
                                sa[k] = sa12[t] < n0 ? sa12[t] * 3 + 1 : (sa12[t] - n0) * 3 + 2;
                            }
                        }
                    }
                }
                return sa;
            }

            private void radixPass(int[] nums, int[] input, int[] output, int offset, int n, int k) {
                int[] cnt = new int[k + 1];
                for (int i = 0; i < n; ++i) {
                    cnt[nums[input[i] + offset]]++;
                }
                for (int i = 0, sum = 0; i < cnt.length; ++i) {
                    int t = cnt[i];
                    cnt[i] = sum;
                    sum += t;
                }
                for (int i = 0; i < n; ++i) {
                    output[cnt[nums[input[i] + offset]]++] = input[i];
                }
            }

            private boolean leq(int a1, int a2, int b1, int b2) {
                return a1 < b1 || (a1 == b1 && a2 <= b2);
            }

            private boolean leq(int a1, int a2, int a3, int b1, int b2, int b3) {
                return a1 < b1 || (a1 == b1 && leq(a2, a3, b2, b3));
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}